package leetcode.秋招.虾皮;

import leetcode.剑指offer.pojo.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ：zsy
 * @date ：Created 2021/10/11 18:58
 * @description：
 */
public class Main {
    public static void main(String[] args) {

    }

    public class Solution {
        /**
         * Note: 类名、方法名、参数名已经指定，请勿修改
         *
         *
         * 给予二叉树的头结点，请返回小偷依据上述原则，能偷到的最多的钱为何？
         * @param node TreeNode类 头结点
         * @return int整型
         */

        Map<TreeNode, Integer> ff = new HashMap<>();
        Map<TreeNode, Integer> gg = new HashMap<>();
        public int getMaxMoney(TreeNode node) {
            // write code here
            dfs(node);
            return Math.max(ff.getOrDefault(node, 0), gg.getOrDefault(node, 0));
        }

        private void dfs(TreeNode node) {
            if (node == null) return;
            dfs(node.left);
            dfs(node.right);
            ff.put(node, node.val + gg.getOrDefault(node.left, 0) + gg.getOrDefault(node.right, 0));
            gg.put(node, Math.max(ff.getOrDefault(node.left, 0), gg.getOrDefault(node.left, 0 ))
                    + Math.max(ff.getOrDefault(node.right, 0), gg.getOrDefault(node.right, 0)));
        }


    }
}
